package cn.edu.bjut.my.thinkinjava._20200429_30_BackTrack;

/**
 * 本例测试全排列
 *
 * 题目：给定字符串，打印出其全排列
 *
 * 思路1：递归
 * 1.1对于char[] cs，全排列=首字母+cs.subArray(1,sc.length)的全排列
 * 1.2对于char[] cs,for 循环，使得每个字母轮流当做首字母
 * 1.3递归参数 char[] cs,下一次递归cs的开始index
 * 1.4递归结束标记 当index==cs的length时，结束并打印
 */
public class Permutation {
    private int count = 0;

    public void permutationFull(String s) {
        long l = System.currentTimeMillis();
        char[] chars = s.toCharArray();
        fn(chars, 0, chars.length);
        System.out.println(System.currentTimeMillis() - l);
    }

    private void fn(char[] chars, int i, int j) {
        if (i == chars.length) {
            for (char c : chars) {
                System.out.print(c);
            }
            System.out.print("   "+ ++count + "   \r\n");
        }
        for (int t = i; t < chars.length; t++) {
            char c = chars[i];
            chars[i] = chars[t];
            chars[t] = c;
            fn(chars, i + 1, j);
            c = chars[i];
            chars[i] = chars[t];
            chars[t] = c;
        }
    }

    public static void main(String[] args) {
        new Permutation().permutationFull("1234");
    }
}
